package zijie;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 *
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 *
 *
 */
public class RestoreIpAddresses_93_16 {
    /**
     * 回溯散发
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {

        List<String> ans = new ArrayList<>();
        if(s == null || s.length() == 0){
            return ans;
        }
        backTrack(s,ans,0,new ArrayList<>());
        return ans;
    }

    private void backTrack(String s,List<String> ans,int pos, List<String> tmp){

        if(tmp.size() == 4){
            if(pos == s.length()){
                ans.add(String.join(".",tmp));
            }
            return;
        }

        for (int i = 1; i < 4; i++) {
            if(pos + i > s.length()){
                break;
            }
            String segment = s.substring(pos,pos + i);
            int val = Integer.valueOf(segment);
            if(segment.length() > 1 && segment.startsWith("0")){
                continue;
            }
            if(i == 3 && val > 255){
                continue;
            }

            tmp.add(segment);
            backTrack(s,ans,pos + i,tmp);
            tmp.remove(tmp.size() - 1);
        }

    }

    public List<String> restoreIpAddresses2(String s) {
        List<String> res= new ArrayList<>();
        if(s == null || s.length() == 0){
            return res;
        }
        dfs2(s,res,0,new ArrayList<>());
        return res;


    }

    public void dfs2(String s,List<String> res,int pos,List<String> tmp) {

        if(tmp.size() == 4){
            if(pos == s.length()){
                res.add(String.join(",",tmp));
            }
            return;
        }
        for (int i = 1; i < 4; i++) {
            if(pos+i > s.length()){
                break;
            }
            String segment = s.substring(pos,pos + i);
            int val = Integer.valueOf(segment);
            if(segment.length() > 1 && segment.startsWith("0")){
                continue;
            }
            if(i == 3 && val > 255){
                continue;
            }
            tmp.add(segment);
            dfs2(s,res,pos + i,tmp);
            tmp.remove(tmp.size() - 1);
        }

    }



}
